#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "list.h"


void list_dump (const char *what, list_t *l)
{
    int i;
    printf ("%s: #%p\t cnt %d\t size %d\t elems %p\n",
            what, l, l->cnt, l->size, l->elems);
    for (i = 0; i < l->cnt; i++) {
        fprintf (stdout, "  #%d: %p at &%p\n", i, l->elems[i], &l->elems[i]);
    }
}


int list_grow (list_t* l, int size)
{
    if (l->flags & LIST_F_NOTGROWS)
        return -1;

    l->size = size;
    if (unlikely(l->size == 0))
        return 0;

    l->elems =	(void **)realloc(l->elems,
            sizeof(void *) * l->size);

    return 0;
}


int list_init (list_t *l, int size, elem_free_func cb_free)
{
    if (!l) return -1;

    memset(l, '\0', sizeof(*l));
    l->size = size;
    l->cb_free = cb_free;

    if (l->size <= 0) return 0;
    l->elems = calloc(1, sizeof(void *) * l->size);
    if (!l->elems)
        return -1;

    return 0;
}

list_t* list_new (int size, elem_free_func cb_free)
{
    list_t *l = NULL;

    l = malloc(sizeof(list_t));
    if (!l) return NULL;

    list_init(l, size, cb_free);
    l->flags |= LIST_F_ALLOCATED;

    return l;
}


/*
 * 因为 gl->elems 是 (void **)（指针的指针）, 那么
 * 在qsort函数中返回比较的元素是 (void **)，
 * 所以我们需要一个跳板函数将 (void **) -> (void *)
 */
static __thread
int (*list_cmp_curr) (const void *, const void *);

static __inline
int list_cmp_trampoline (const void *_a, const void *_b) {
    const void *a = *(const void **)_a, *b = *(const void **)_b;

    return list_cmp_curr(a, b);
}

int list_sort (list_t *l,
        int (*cmp)(const void *_a, const void *_b))
{
    list_cmp_curr = cmp;
    qsort(l->elems, l->cnt,
            sizeof(*l->elems), list_cmp_trampoline);
    l->flags |= LIST_F_SORTED;

    return 0;
}

void* list_elem (list_t *l, int index)
{
    BUG_ON(l == NULL);

    if (likely(l->cnt > index))
        return l->elems[index];
    return NULL;
}


void* list_find (list_t *l, const void *elem,
        int (*cmp)(const void *_a, const void *_b))
{
    BUG_ON(l == NULL);
    BUG_ON(elem == NULL);
    BUG_ON(cmp == NULL);
    void *e;

    if (l->flags & LIST_F_SORTED) {
        void **ep;
        list_cmp_curr = cmp;
        ep = (void **)bsearch(&elem, l->elems, l->cnt,
                sizeof(*l->elems), list_cmp_trampoline);

        return ep ? *ep : NULL;
    }

    int i = 0;
    LIST_FOREACH (l, i, e) {
        if (!cmp (elem, e))
            return e;
    }

    return NULL;
}


void list_free_cb (list_t *l, void *ptr)
{
    BUG_ON(l == NULL);
    if (l->cb_free && ptr)
        l->cb_free(ptr);
}


int list_add_noduplicate (list_t *l, void *elem,
        int (*cmp)(const void *_a, const void *_b))
{
    BUG_ON(l == NULL);
    BUG_ON(elem == NULL);
    BUG_ON(cmp == NULL);

    if (list_find(l, elem, cmp))
        return 0;

    if (l->cnt + 1 >= l->size)
        list_grow(l, l->size ? l->size * 2 : 16);

    l->elems[l->cnt++] = elem;
    l->flags &= ~LIST_F_SORTED;

    return 0;
}


int list_add (list_t *l, void *elem)
{
    BUG_ON(l == NULL);
    BUG_ON(elem == NULL);
    if (l->flags & LIST_F_UNIQUE)
        fprintf(stdout, "warning: the list not allow duplicates,"
                "you should use list_add_noduplicate\n");

    if (l->cnt + 1 > l->size)
        list_grow(l, l->size ? l->size * 2 : 16);

    l->elems[l->cnt++] = elem;
    l->flags &= ~LIST_F_UNIQUE;
    l->flags &= ~LIST_F_SORTED;

    return 0;
}


void* list_remove_index(list_t *l, int idx)
{
    BUG_ON(l == NULL);
    BUG_ON(idx < 0);
    void *e = NULL;

    if (likely(l->cnt > (idx+1))) {
        e = l->elems[idx];
        memmove(&l->elems[idx],
                &l->elems[idx + 1],
                sizeof(*l->elems) * (l->cnt - (idx+1)));
    }
    l->cnt--;

    return e;
}


void* list_remove (list_t *l, void *elem)
{
    BUG_ON(l == NULL);
    BUG_ON(elem == NULL);
    void *e;
    int i = 0;

    LIST_FOREACH(l, i, e) {
        if (e == elem) {
            list_remove_index(l, i);
            return e;
        }
    }

    return NULL;
}

void* list_remove_cmp (list_t *l, void *elem,
        int (*cmp)(const void *_a, const void *_b))
{
    BUG_ON(l == NULL);
    BUG_ON(elem == NULL);
    BUG_ON(cmp == NULL);
    int i = 0;
    void *e;

    LIST_FOREACH(l, i, e) {
        if (e == elem || !cmp(e, elem)) {
            list_remove_index(l, i);
            return e;
        }
    }

    return NULL;
}


int list_multi_remove_cmp (list_t *l, void *elem,
        int (*cmp)(const void *_a, const void *_b))
{
    BUG_ON(l == NULL);
    BUG_ON(elem == NULL);
    BUG_ON(cmp == NULL);
    void *e;
    int i, cnt = 0;

    LIST_FOREACH(l, i, e) {
        if (e == elem || !cmp(e, elem)) {
            list_remove_index(l, i);
            i -= 1;  // fix bug
            list_free_cb(l, e);
            cnt++;
        }
    }

    return cnt;
}


/* 默认copy 指针 */
void* list_onlycopy_ptr (void *s, void *mt)
{
    (void)mt;
    return (void *)s;
}


int list_copy_to (list_t *dst, list_t *src,
        void* (*copy)(void* _d, void *_s),
        void* match)
{
    BUG_ON(dst == NULL);
    BUG_ON(src == NULL);
    int i = 0;
    void *s, *d = NULL;

    if (!copy) copy = list_onlycopy_ptr;

    LIST_FOREACH (src, i, s) {
        if (!s)
            break;
        d = copy(s, match);
        if (d)
            list_add(dst, d);
    }
    dst->cb_free = src->cb_free;
    dst->flags = src->flags;

    return 0;
}

void list_free (list_t *l)
{
    int i;

    if (l) {
        for (i = 0; i < l->cnt; i ++) {
            if (l->cb_free)
                l->cb_free(l->elems[i]);
            else
                free(l->elems[i]);

        }
        free(l->elems);
        l->elems = NULL;

        if (l->flags & LIST_F_ALLOCATED) {
            free(l);
            l = NULL;
        }
    }
}


list_t* list_copy (list_t *src,
        void* (*copy)(void* _d, void *_s),
        void* match)
{
    BUG_ON(src == NULL);
    list_t *dst = NULL;

    dst = list_new(src->size, src->cb_free);

    if (list_copy_to(dst, src, copy, match) != 0) {
        list_free(dst);
        dst = NULL;
    }

    return dst;
}



